package HOT;

/**
 * Author  zxy
 * Date  2023/7/7 11:23
 */

/*
* 在一个由 '0' 和 '1' 组成的二维矩阵内
* 找到只包含 '1' 的最大正方形，并返回其面积。
* */

public class MaximalSquare_221 {
    public int maximalSquare(char[][] matrix) {

        // 动态规划
        int row = matrix.length;
        int col = matrix[0].length;

        // for (int i = 0; i < row; i++) {
        //     for (int j = 0; j < col; j++) {
        //         System.out.print(matrix[i][j] + " ");
        //     }
        //     System.out.println();
        // }

        int[][] dp = new int[row][col];
        int maxm = 0;

        // 初始化 dp 数组
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dp[i][j] = matrix[i][j] - '0';

                if (maxm == 0 && dp[i][j] == 1) {
                    maxm = 1;
                }
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                // 若 matrix[i][j] 为0，则不可能组成正方形
                if (matrix[i][j] == '0') {
                    continue;
                }

                // 若左边或上边有一个为0，则不可能组成正方形
                if (dp[i - 1][j] == 0 || dp[i][j - 1] == 0) {
                    continue;
                }

                int minm = Math.min(dp[i - 1][j], dp[i][j - 1]);


                if (dp[i - minm][j - minm] != 0) {
                    dp[i][j] = minm + 1;
                }
                else {
                    dp[i][j] = minm;
                }

                maxm = Math.max(maxm, dp[i][j]);
            }
        }

        // for (int i = 0; i < row; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }

        return maxm * maxm;
    }
}
